package 调整数组顺序使奇数位于偶数前面;



//题目描述
//输入一个整数数组，实现一个函数来调整该数组中数字的顺序，
// 使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
public class Solution
{
    public void reOrderArray(int [] array)
    {
        //方法一，新建数组，依次遍历数组，%2，奇数在前，偶数在后，时间2n，空间n
        if (array==null||array.length==0)
            return;

        int oddcount=0;
        int oddbegin=0;
        int[] temp=new int[array.length];
        for (int i = 0; i < array.length; i++)
        {
            if ((array[i]&1)==1)
                oddcount++;
        }
        for (int i = 0; i < array.length; i++)
        {
            if ((array[i]&1)==1)//奇数
                temp[oddbegin++]=array[i];
            else
                temp[oddcount++]=array[i];
        }
        for (int i = 0; i < array.length; i++)
        {
            array[i]=temp[i];
        }
    }
    public void reOrderArray1(int [] array)
    {
        //使用插入排序的思想
        //偶数代码中不处理，入到奇数，所在位置大于已排好序的奇数个数，就把这个奇数一直往前换，直到把前面的偶数换出来
        int count=0;
        for (int i = 0; i < array.length; i++)
        {
            if ((array[i]&1)==1)
            {
                int j=i;
                while (j>count)
                {
                    int temp=array[j];
                    array[j]=array[j-1];
                    array[j-1]=temp;
                    j--;
                }
                count++;
            }
        }
    }
}
